package com.njupt.Tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/12/4 10:04
 * @Description: 617. 合并二叉树
 * @Version: 1.0
 */


public class MergeTrees {

    /**
     * 通过
     * @param root1
     * @param root2
     * @return
     */
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {

        if(root1 == null) return root2;
        if(root2 == null) return  root1;
        root1.val += root2.val;
        root1.left = mergeTrees(root1.left,root2.left);
        root1.right = mergeTrees(root1.right,root2.right);
        return root1;
    }

    /**
     * 通过
     * @param root1
     * @param root2
     * @return
     */
    public TreeNode mergeTrees2(TreeNode root1, TreeNode root2) {
        if(root1 == null && root2 == null) return null;

        if(root1 == null && root2 != null){
            return root2;
        }
        if(root1 != null && root2 == null){
            return root1;
        }

        TreeNode root = new TreeNode(root1.val + root2.val);

        root.left = mergeTrees2(root1.left,root2.left);
        root.right = mergeTrees2(root1.right,root2.right);
        return root;

    }


    /**
     * 未通过的原因是如果这个地方
     * if(root1 == null && root2 != null){
     *             return new TreeNode(root2.val);
     *         }
     *如果递归到某一层之后一个节点不空，一个节点未空，那么就直接返回了一个新节点，
     * 原来树上的节点就不会再递归下去了
     * @param root1
     * @param root2
     * @return
     */
    public TreeNode mergeTrees3(TreeNode root1, TreeNode root2) {
        if(root1 == null && root2 == null) return null;

        if(root1 == null && root2 != null){
            return new TreeNode(root2.val);
        }
        if(root1 != null && root2 == null){
            return new TreeNode(root1.val);
        }

        TreeNode root = new TreeNode(root1.val + root2.val);

        root.left = mergeTrees3(root1.left,root2.left);
        root.right = mergeTrees3(root1.right,root2.right);
        return root;

    }

    /**
     * 先序遍历非递归算法
     * @param root1
     * @param root2
     * @return
     */
    public TreeNode mergeTrees1(TreeNode root1, TreeNode root2) {
        Deque<TreeNode> stack1 = new LinkedList<>();
        Deque<TreeNode> stack2 = new LinkedList<>();

        TreeNode cur1 = root1;
        TreeNode cur2 = root2;
        while( (cur1 != null || !stack1.isEmpty())
                || (cur2 != null || !stack2.isEmpty())){

            if(cur1 != null && cur2 != null){
                //访问根节点
                cur1.val += cur2.val;
                stack1.push(cur1);
                stack2.push(cur2);

                cur1 = cur1.left;
                cur2 = cur2.left;
            }else if(cur1 == null && cur2 != null){
                cur1 = cur2;

                cur1 = stack1.pop();
                cur1 = cur1.right;

                cur2 = stack2.pop();
                cur2 = cur2.right;
            } else if (cur1 != null && cur2 == null) {
                cur1 = stack1.pop();
                cur1 = cur1.right;

                cur2 = stack2.pop();
                cur2 = cur2.right;

            } else  {
                cur1 = stack1.pop();
                cur1 = cur1.right;

                cur2 = stack2.pop();
                cur2 = cur2.right;
            }
        }

        return root1;
    }

    public static void main(String[] args) {
//        TreeNode root1 = new TreeNode(1);
//        root1.left = new TreeNode(3);
//        root1.right = new TreeNode(2);
//        root1.left.left = new TreeNode(5);
//
//        TreeNode root2 = new TreeNode(2);
//        root2.left = new TreeNode(1);
//        root2.right = new TreeNode(3);
//        root2.left.right = new TreeNode(4);
//        root2.right.right = new TreeNode(7);


        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(2);
        root1.left.left = new TreeNode(3);

        TreeNode root2 = new TreeNode(1);
        root2.right = new TreeNode(2);
        root2.right.right = new TreeNode(3);

        MergeTrees test = new MergeTrees();
        TreeNode root = test.mergeTrees1(root1, root2);
        System.out.println();

    }
}
